# 凝聚聚类

"""
凝聚聚类（agglomerative clustering）是一种基于“合并”原则的聚类算法：最初每个数据点都是独立的簇，然后逐步合并最相似的簇，直到达到指定的簇数量为止。
在 scikit-learn 中，通过设置簇的最终数量作为停止条件。此外，它还使用“链接准则”来定义两个簇之间的相似度。


scikit-learn 中实现了以下三种选项。
ward
    默认选项。ward 挑选两个簇来合并，使得所有簇中的方差增加最小。这通常会得到大
    小差不多相等的簇。
average
    average 链接将簇中所有点之间平均距离最小的两个簇合并。
complete
    complete 链接（也称为最大链接）将簇中点之间最大距离最小的两个簇合并。

ward 适用于大多数数据集，在我们的例子中将使用它。如果簇中的成员个数非常不同（比
如其中一个比其他所有都大得多），那么 average 或 complete 可能效果更好。

"""
import mglearn.plots
from matplotlib import pyplot as plt
from sklearn.datasets import make_blobs

# 凝聚聚类用迭代的方式合并两个最近的簇
mglearn.plots.plot_agglomerative_algorithm()
plt.show()

'''
凝聚聚类的过程如下：
    1.初始时，每个点都是一个独立的簇。
    2.在每一步中，距离最近的两个簇会被合并。
    3.例如，在前四个步骤中，两个单点簇会被合并成一个两点簇。
    4.在第五步中，其中一个两点簇会扩展为三点簇，依此类推。
    5.到第九步时，只剩下三个簇。由于我们指定要找三个簇，算法在此结束。
对于简单的三簇数据，凝聚聚类可以很好地工作。但需要注意的是，凝聚聚类无法对新数据点进行预测，
因此 AgglomerativeClustering 没有 predict 方法。如果需要得到训练集上的簇成员关系，可以使用 fit_predict 方法。
'''

from sklearn.cluster import AgglomerativeClustering
X,y = make_blobs(random_state=1)
agg = AgglomerativeClustering(n_clusters=3)
assignment = agg.fit_predict(X)
mglearn.discrete_scatter(X[:, 0], X[:, 1], assignment)
plt.xlabel("Feature 0")
plt.ylabel("Feature 1")
# plt.show()

'''
正如所料，算法完美地完成了聚类。虽然凝聚聚类的 scikit-learn 实现需要你指定希望
算法找到的簇的个数，但凝聚聚类方法为选择正确的个数提供了一些帮助，我们将在下面讨论。
'''

# 层次聚类与树状图
'''
凝聚聚类会生成层次聚类，整个过程是迭代的。每个点最初是一个独立的簇，然后逐步合并，最终属于某个大簇。
在每个中间步骤，数据都被划分成不同数量的簇。有时，查看所有可能的聚类（从单点簇到最终的大簇）是有帮助的。
例如，通过叠加显示所有可能的聚类，可以更清楚地看到每个簇是如何逐步分解为更小的簇的。
'''

mglearn.plots.plot_agglomerative()
# plt.show()

'''
层次聚类的详细可视化依赖于二维数据，无法用于多于两个特征的数据集。但可以用**树状图（dendrogram）**来可视化层次聚类，它适用于多维数据。
目前 scikit-learn 不支持绘制树状图，但可以通过 SciPy 来实现。SciPy 提供了一个函数，输入数据数组 X 后会计算出一个链接数组（linkage array），
用于编码层次聚类的相似度信息。最后，将这个链接数组传递给 SciPy 的 dendrogram 函数即可绘制树状图。
'''

# 从SciPy中导入dendrogram函数和ward聚类函数
from scipy.cluster.hierarchy import dendrogram, ward
X, y = make_blobs(random_state=0, n_samples=12)
# 将ward聚类应用于数据数组X
# SciPy的ward函数返回一个数组，指定执行凝聚聚类时跨越的距离
linkage_array = ward(X)
# 现在为包含簇之间距离的linkage_array绘制树状图
dendrogram(linkage_array)
# 在树中标记划分成两个簇或三个簇的位置
ax = plt.gca()
bounds = ax.get_xbound()
ax.plot(bounds, [7.25, 7.25], '--', c='k')
ax.plot(bounds, [4, 4], '--', c='k')
ax.text(bounds[1], 7.25, ' two clusters', va='center', fontdict={'size': 15})
ax.text(bounds[1], 4, ' three clusters', va='center', fontdict={'size': 15})
plt.xlabel("Sample index")
plt.ylabel("Cluster distance")
plt.show()

'''
树状图的底部显示了编号为 0 到 11 的数据点，这些点作为单点簇开始聚类。随着层次聚类的进行，每合并两个簇就会在树上添加一个新节点。从下往上观察：
    数据点 1 和 4 首先被合并。
    接着，点 6 和 9 被合并。
    最终，树的顶层形成了两个大分支：
        一个分支包含点 11、0、5、10、7、6 和 9。
        另一个分支包含点 1、4、3、2 和 8。
    这两个分支对应于图中左侧的两个最大簇。
树状图的 y 轴不仅显示了簇的合并顺序，每个分支的长度还表示被合并簇之间的距离。图中用虚线标记的“三个簇”部分显示了最长的分支，
这意味着在从三个簇合并为两个簇的过程中，合并了一些距离较远的点。同样，在将最后两个簇合并为一个簇时，也需要跨越较大的距离。
然而，尽管树状图可以很好地展示层次聚类的过程，凝聚聚类仍然无法处理像“two_moons”这样复杂的形状数据。
不过，我们即将学习的 DBSCAN 算法可以解决这类问题。
'''

